package com.datastructures2.skipTable;

import java.util.Comparator;
import java.util.concurrent.ThreadLocalRandom;

/**
 * @author MaoLin Wang
 * @description
 * @date 2020/9/25 8:50 上午
 */
public class SkipList22<T> {
    public static void main(String[] args) {
        SkipList22<Integer> skipList = new SkipList22<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                if (o1==null&& o2==null){
                    return 0;
                }
                if (o1==null){
                    return -1;
                }
                if (o2==null){
                    return 1;
                }
                return o1-o2;
            }
        });
        skipList.add(1);
        skipList.add(9);
        skipList.add(7);
        skipList.add(4);
        skipList.add(2);
        skipList.add(10);
        skipList.add(122);
        System.out.println(skipList.get(10));
    }
    private HeadIndex<T> head;
    private Comparator<T> comparator;

    public SkipList22() {
        this.head=new HeadIndex<>(new Node<>(null,null),null,null,1);
        this.comparator = (t1,t2)->((Comparable<T>)t1).compareTo(t2);
    }

    public SkipList22(Comparator<T> comparator) {
        this.head = new HeadIndex<>(new Node(null, null), null, null, 1);
        this.comparator = comparator != null ? comparator : (t1,t2)->((Comparable<T>)t1).compareTo(t2);
    }
    public void  add(T value){
        if (value==null){
            throw new NullPointerException("value is null");
        }
        Node<T> preNode = findPreIndexNode(value,true);
        if (preNode!=null && comparator.compare(preNode.value,value)==0){
            return;
        }
        //加入到链表
        Node<T>p,n,newNode;
        int result;
        for (p=preNode;;){
            n=p.next;
            if (n==null){
                result=1;
            }else {
                result=comparator.compare(n.value,value);
                if (result==0){
                    return;
                }
            }
            if (result>0){
                p.next=newNode=new Node<>(value,n);
                break;
            }
            p=n;
        }

        int random = ThreadLocalRandom.current().nextInt();
        if ((random&1)==0){ //最后一位为0时才建立层索引
            int level=0;
            //生成随机level，从倒数第二位开始，有几个1层级就是几
            while (((random>>>=1)&1)!=0){
                level++;
            }
            HeadIndex<T>oldHead=this.head;
            int maxLevel=oldHead.level;
            Index<T> idx=null;
            if (level<=maxLevel){//不需要建立新的头节点，直接将插入节点那一竖列连接起来
                for (int i = 0; i < level; i++) {
                    idx=new Index<>(newNode,idx,null);
                }
            }else {
                level=maxLevel+1;
                for (int i = 0; i < level; i++) {
                    idx=new Index<>(newNode,idx,null);
                }
                //新的头节点已经连接好横向和竖向
                this.head=new HeadIndex<>(oldHead.node,oldHead,idx,level);
                idx=idx.down;//TODO
            }
            //连接横线，从旧头节点开始
            Index<T>ohx,r;
            int currentLevel;
            for(ohx=oldHead,currentLevel=oldHead.level;ohx!=null;){
                r=ohx.right;
                if (r!=null){
                    int compare = comparator.compare(r.node.value, value);
                    if (compare<0){
                        ohx=r;
                        continue;
                    }
                }
                if (level<currentLevel){
                    ohx=ohx.down;
                }else {
                    idx.right=r;
                    ohx.right=idx;
                    ohx=ohx.down;
                    idx=idx.down;
                }
                currentLevel--;
            }
        }


    }


    public T get(T value){
        if (value==null){
            throw new NullPointerException("value is null");
        }
        Node<T> preNode=findPreIndexNode(value,true);
        if (preNode!=null && comparator.compare(preNode.value,value)==0){
            return value;
        }
        Node<T>next=preNode.next;
        if (next!=null){
            int result = comparator.compare(next.value, value);
            if (result==0){
                return next.value;
            }else if (result>0){
                return null;
            }
            next=next.next;
        }
        return null;
    }
    private Node<T> findPreIndexNode(T value, boolean contain) {
        /*
         * q---->r---->r
         * |     |
         * |     |
         * v     v
         * d     d
         * q = query
         * r = right
         * d = down
         */
        // 从头节点开始查找，规律是先往右再往下
        Index<T> q = this.head;
        Index<T> r, d;
        Comparator<T> cmp = this.comparator;
        for(;;) {
            r = q.right;
            if (r != null) {
                // 包含value的索引，正好有
                if (contain && cmp.compare(r.node.value, value) == 0) {
                    return r.node;
                }
                // 如果右边的节点比value小，则右移
                if (cmp.compare(r.node.value, value) < 0) {
                    q = r;
                    continue;
                }
            }
            d = q.down;
            // 如果下面的索引为空了，则返回该节点
            if (d == null) {
                return q.node;
            }
            // 否则，下移
            q = d;
        }
    }

    private Node<T> findPreNode(T value) {
        Index<T> temp=this.head;
        Index<T> r,d;
        for(;;){
            r=temp.right;
            if (r!=null){
                int result = comparator.compare(r.node.value, value);
                if (result==0){
                    return r.node;
                }
                if (result<0){
                    temp=r;
                    continue;
                }

            }else {
                d=temp.down;
                if (d==null){
                    return temp.node;
                }
                //下移
                temp=d;
            }
        }
    }

    /**
     * 头节点
     * @param <T>
     */
    private static class HeadIndex<T> extends Index<T>{
        int level;
        public HeadIndex(Node<T> node, Index<T> down, Index<T> right,int level) {
            super(node, down, right);
            this.level=level;
        }
    }

    /**
     * 索引节点
     * 引用数据节点，另包括down和right两个索引节点
     * @param <T>
     */
    private static class Index<T>{
        Node<T> node;
        Index<T> down;
        Index<T>right;

        public Index(Node<T> node, Index<T> down, Index<T> right) {
            this.node = node;
            this.down = down;
            this.right = right;
        }
    }
    /**
     * 数据节点 包括数据值和next引用，单链表结构
     * @param <T>
     */
    static class Node<T> {
        T value;
        Node<T> next;

        public Node(T value, Node<T> next) {
            this.value = value;
            this.next = next;
        }
        @Override
        public String toString() {
            return (value==null?"h0":value.toString()) +"->" + (next==null?"null":next.toString());
        }
    }
}
